/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 **********************************************************************/

#include <geos/index/intervalrtree/SortedPackedIntervalRTree.h>
#include <geos/index/intervalrtree/IntervalRTreeNode.h>
#include <geos/index/intervalrtree/IntervalRTreeLeafNode.h>
#include <geos/index/intervalrtree/IntervalRTreeBranchNode.h>
#include <geos/index/ItemVisitor.h>
#include <geos/util/UnsupportedOperationException.h>

#include <algorithm>

#ifdef _MSC_VER
#pragma warning(disable : 4127)
#endif

namespace geos {
namespace index {
namespace intervalrtree {
//
// private:
//
void
SortedPackedIntervalRTree::init()
{
	if (root != nullptr) return;

	root = buildTree();
}

const IntervalRTreeNode *
SortedPackedIntervalRTree::buildTree()
{
	branches.reserve(leaves.size() - 1);

	// now group nodes into blocks of two and build tree up recursively
	std::vector<const IntervalRTreeNode*> src{leaves.size()};
	std::vector<const IntervalRTreeNode*> dest;
	std::transform(leaves.begin(), leaves.end(), src.begin(), [](const IntervalRTreeLeafNode & n) { return &n; });

	// sort the leaf nodes
	std::sort( src.begin(), src.end(), IntervalRTreeNode::compare );

	while (true)
	{
		buildLevel(src, dest);

		if (dest.size() == 1)
		{
		    return dest[0];
		}

		std::swap(src, dest);
	}
}

void
SortedPackedIntervalRTree::buildLevel(IntervalRTreeNode::ConstVect & src, IntervalRTreeNode::ConstVect & dest)
{
	level++;

	dest.clear();

	for (size_t i = 0, ni = src.size(); i < ni; i += 2)
	{
		const IntervalRTreeNode * n1 = src[i];

		if ( i + 1 < ni )
		{
			const IntervalRTreeNode * n2 = src[i + 1];

			branches.emplace_back(n1, n2);
			dest.push_back(&branches.back());
		}
		else
		{
			dest.push_back( n1);
		}
	}
}

//
// protected:
//

//
// public:
//

void
SortedPackedIntervalRTree::insert( double min, double max, void * item)
{
	if (root != nullptr)
		throw util::UnsupportedOperationException( "Index cannot be added to once it has been queried");

	leaves.emplace_back(min, max, item);
}

void
SortedPackedIntervalRTree::query( double min, double max, index::ItemVisitor * visitor)
{
	init();

	root->query( min, max, visitor);
}

} // geos::intervalrtree
} // geos::index
} // geos
